Image data is generally formed from many pixels. The amount of image data is very large because one pixel has a plurality of color components and one color component is expressed by multiple bits. To save such data or transfer it in a short time, a compression encoding technique is indispensable. Procedures to encode digital image data obtained by an image sensing device or the like will be explained. First, image data is divided into tiles each having a desired rectangular size. Each tile is divided into a plurality of MBs (Macro Blocks) in a predetermined two-dimensional array. The MB serves as the processing unit of encoding processing (see FIG. 5).
The MB data is orthogonally transformed from color space data into transform coefficients in the frequency space. In lossy encoding, the transform coefficients are quantized to further increase the compression efficiency. When the image data pattern lies across a plurality of blocks, coefficient prediction is done for the quantized transform coefficients in accordance with respective frequency bands, further decreasing the level of the transform coefficients. When the quantization value changes depending on the coefficient position in the block or changes between blocks, an image data pattern lying across a plurality of blocks does not always hold a correlation corresponding to the frequency band of the transform coefficient. For this reason, coefficient prediction cannot always suppress the level of the transform coefficient. In this case, coefficient prediction processing may be omitted. The quantized transform coefficients having undergone the coefficient prediction are scanned as two-dimensional data and sorted into one-dimensional data so that significant coefficients (significant data) are positioned first and then insignificant coefficients (insignificant data), i.e., a run (zeros) continues after the significant coefficients. The sorted one-dimensional data are entropy-encoded, generating an encoded stream. By decoding the generated encoded stream, the image can also be reconstructed.
General image encoding apparatuses, which encode each pixel block, as represented by JPEG, MPEG2, MPEG4, and JPEG XR, adopt run-length encoding as entropy encoding. In run-length encoding, the length of a run is encoded. When encoding an image, transform coefficients in a two-dimensional array after frequency conversion or subsequent quantization are converted into a one-dimensional array. The one-dimensional array undergoes run-length encoding. As conversion (scan conversion) from a two-dimensional array into a one-dimensional array becomes more proper, the encoding efficiency becomes higher. A typical example of frequency transformation is DCT. One DC coefficient value is obtained at the upper left corner among 8×8 transform coefficients in a two-dimensional array attained by DCT transform. The 63 remaining transform coefficients are AC coefficients, and component values having higher frequencies are arranged in the order from the upper left to lower right. A scan order considered to be effective for scanning transform coefficients of a two-dimensional array into a one-dimensional array is zigzag scanning shown in FIG. 3A (numbers in squares shown in FIG. 3A indicate turns of scanning, and the name “zigzag scanning” is taken from the zigzag locus of turns indicated by the numbers).
However, a predetermined scan pattern, like a “zigzag” pattern, does not always contribute to the encoding efficiency because of the following three reasons.
First, when conversion is executed across blocks to suppress a block distortion, the edge is emphasized, increasing the variance of transform coefficients and also increasing the level of the transform coefficients. In this case, the level of a lower right transform coefficient in the two-dimensional array does not always become low. Hence, the scan order in which transform coefficients are scanned from the upper left corner to lower right corner of a block is not always optimum. Second, if pixels in a block have a horizontal or vertical dependence, the frequency bands of transform coefficients tend to be biased in accordance with the dependence. In this case, scan orders which differ between the horizontal and vertical directions, as shown in FIGS. 3B and 3C, are suitable. Finally, when a texture lies across blocks, the biases of transform coefficients in the blocks tend to be the same. In this case, the level of the coefficients can be suppressed by performing coefficient prediction for quantized transform coefficients. The bias of the frequency bands of transform coefficients changes depending on the prediction method, so a scan pattern corresponding to a prediction method is required. For these reasons, it is desirable to adaptively select a scan order optimum for an input image and encoding method (see, e.g., Japanese Patent Laid-Open No. 2004-032788 (to be referred to as reference 3)).
Further, a method of changing the scan order for each block is suited to an encoding method in which an MB is subdivided into blocks and the quantization value and coefficient prediction method can be changed for each block, as typified by JPEG XR (see, e.g., Japanese Patent Laid-Open No. 2006-191628 (to be referred to as reference 1) and Japanese Patent Laid-Open No. 7-050836 (to be referred to as reference 2)). For example, according to the scan order determination method described in reference 1, an MB made up of 16×16 pixels is divided into blocks A to P each having a size of 4×4 pixels, as shown in FIG. 4. In scan conversion processing, the transform coefficients of the respective blocks are read in the order of blocks A to P, and scan conversion is performed. For example, after all the transform coefficients of block A are input, they are sorted in a predetermined scan order to output the transform coefficients. The scan conversion results of block A are analyzed, i.e., the transform coefficients are analyzed in the scan order after sorting. Then, the scan order of the next block B is determined. In this way, the scan order of a block to undergo scan conversion is determined causally based on a block having undergone scan conversion before the target block.
A detailed example of the scan order determination method will be described with reference to the flowchart of FIG. 6. Assume that a two-dimensional array to be converted has 4×4 transform coefficients.
Statistical information ScanTotals (e.g., FIG. 7A) is prepared by statistically obtaining the position of one of 4×4 transform coefficients where a significant coefficient tends to be generated. Assume that {t*N, t*(N−1), t*(N−2), . . . , t} is set as the initial value of the statistical information ScanTotals. In general, a small integer (2 or 4) is selected as t. The t value may be determined based on a quantization parameter used in quantization. The maximum bit length of each element of statistical information can be fixed by resetting the statistical information after a predetermined period. Scan order information ScanOrder[ ] is also prepared, which indicates an order in which a significant coefficient tends to be generated statistically (FIG. 7B). In FIG. 7B, a lower-case alphabetic letter corresponds to the position of a lower-case alphabetic letter in a block shown in FIG. 4. FIGS. 7A and 7B reveal that a significant coefficient is statistically highly likely to be generated at a transform coefficient position “d”. That is, in FIGS. 7A and 7B, the first coefficient converted into a one-dimensional array is one at the position “d”.
Note that the image encoding side and image decoding side suffice to take a common scan order, and numerical values in FIGS. 7A and 7B are merely an example. For example, in an application to an encoding apparatus which is premised on horizontal coefficient prediction, a scan order table exhibiting a scan order which gives priority to horizontal scanning is prepared (see FIG. 3B). Also, in an application to an encoding apparatus which is premised on vertical coefficient prediction, a scan order table which gives priority to vertical scanning is prepared (see FIG. 3C).
In S801, one transform coefficient C[x] (0≦x≦15) in a block having undergone scan conversion is acquired in the one-dimensional order (x=0 in the initial state). In S802, it is determined whether the transform coefficient C[x] acquired in S801 is a run (zeros). If the transform coefficient C[x] is a run, the process advances to determination in S806. If the transform coefficient C[x] is a significant coefficient (nonzero), processing in S803 is executed. If the process shifts to S803, statistical information ScanTotals[x] of the transform coefficient C[x] determined to be a significant coefficient is incremented. In S804, the magnitude relationship between pieces of statistical information ScanTotals[x] and ScanTotals[x−1] is determined. If ScanTotals[x] is larger than ScanTotals[x−1], this means that the significant coefficient generation count is higher at the position of the transform coefficient C[x] than at that of the transform coefficient C[x−1]. In S805, therefore, swapping processing is done for a coefficient position ScanOrder and ScanTotals corresponding to the scan order. In S803, if the statistical information ScanTotals[x] is smaller than ScanTotals[x−1], no scan order change processing is executed.
Detailed swapping processing in S805 will be explained. In the swapping processing, for example, the following calculation is done to swap the coefficient positions ScanOrder[x] and ScanOrder[x−1]:                Temp=ScanOrder[x−1]        ScanOrder[x−1]=ScanOrder[x]        ScanOrder[x]=Temp        
On the other hand, for example, the following calculation is executed to swap the pieces of statistical information ScanTotals[x] and ScanTotals[x−1]:                Temp=ScanTotals[x−1]        ScanTotals[x−1]=ScanTotals[x]        ScanTotals[x]=Temp        
If acquisition of transform coefficients in the block has not been completed in S806, the process advances to S807 to prepare for acquisition of the next coefficient in order to determine the scan order of the next block. If acquisition of all coefficients in the block has been completed, the scan order determination sequence ends.
As described above, the coefficient position ScanOrder[x−1] corresponding to the scan order x−1 is determined causally using pieces of statistical information ScanTotals[x] and ScanTotals[x−1] corresponding to the scan orders x and x−1. By repeating scan conversion, the scan order can be substantially optimized stepwise. Since the scan order can be determined causally, information explicitly notifying a decoding apparatus of the scan order need not be added to an encoded stream.
However, according to the conventional scan order determination method, blocks to undergo scan conversion need to be processed sequentially, and the scan order can be determined for only one coefficient per cycle. Also, the conventional scan order determination method cannot start scan conversion of the next block before completion of scan conversion of one block. That is, a plurality of blocks cannot undergo scan conversion simultaneously.